'''
https://leetcode.cn/problems/search-insert-position/?envType=study-plan-v2&envId=top-interview-150
'''
import bisect
from typing import List

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # >= 的最左位置
        # return bisect.bisect_left(nums, target)
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + r >> 1
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return l